322. Coin Change

1. 문제

1-1. 원문

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:
Input: coins = [2], amount = 3
Output: -1

Example 3:
Input: coins = [1], amount = 0
Output: 0

Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

1-2. 내용 번역

코인의 종류와 합계가 주어졌을 때, 코인의 종류를 조합해서 합계를 만들어낼 수 있는지, 있다면 최소한의 코인 갯수를 없다면 -1을 리턴해라. 각 종류의 코인 갯수는 무한하다고 가정한다.

2. 문제 이해

2-1. 내용 이해

Example1을 예로 설명해보면, 코인은 1짜리, 2짜리, 5짜리 코인 3종류가 있고, 합계는 11이다. 1짜리 코인 11개를 이용해서 합계 11을 만들 수도 있고, 2짜리 코인 5개, 1짜리 코인 1개를 이용해서 합계를 만들 수도 있다. 이렇게 조합해볼 때 코인의 갯수를 가장 적게 쓰는 조합은 5짜리 코인2개, 1짜리 코인 1개를 사용하는, 총 3개의 코인을 사용해서 만든 합계이다. 따라서 이 경우에는 3을 리턴한다.
Example2의 경우는 코인이 2짜리 코인 한 종류만 있다. 때문에 2짜리 코인을 얼마를 쓰더라도 합계 3을 만들 수는 없다. 따라서 이 경우는 -1을 반환해야 한다.

2-2. 접근법 생각

배낭의 무게는 합계, 물건의 무게는 코인의 종류, 물건의 가치는 이때까지 쓴 코인의 최소 개수로 생각하자. 그리고 합계를 만들어낼 수 있는지 없는지의 여부도 중요하기 때문에 구분이 필요하다는 것을 염두해두자.

2-3. 적용한 풀이

Knapsack BottomUp (Tabulation)

tabulation을 사용하면 Base Condition이나 Limit Edge Case등이 자연스럽게 제거되는 측면이 있기 때문에 recursion보다 사용하기 편한 측면이 있다.

3. 구현

3-1. 최초 구현

최초 구현은 접근법 생각에서 서술한 것을 그대로 코드로 옮겼다. 이렇게 풀이를 하니 512ms의 속도로 하위 7.69%의 성능을 보였다. 때문에 최적화의 필요성을 느끼게 되었고, 줄일 수 있는 부분은 3-2.에서 다시 설명하도록 한다.

class Solution {
    var MAX_VALUE = Integer.MAX_VALUE

    fun coinChange(coins: IntArray, amount: Int): Int {
        MAX_VALUE = amount+10 

        return bottomUp(coins, amount)   
    }

    fun bottomUp(coins: IntArray, amount: Int): Int {
	    // 배열 구성은 코인의 종류*(0~합계 사이의 수)=합계를 만들 수 있는 최소 코인 개수
        val memo = Array(coins.size){IntArray(amount+1){MAX_VALUE}}

        for(idx in 0..coins.size-1) {
            memo[idx][0] = 0
        }

		// 다음 for문에서 인덱스-1을 요청하는 경우가 있기 때문에 인덱스 0의 경우에 대해서 따로 처리한다.
        for(curAmount in 1..amount) {
            memo[0][curAmount] = if(curAmount%coins[0] == 0) curAmount/coins[0] else MAX_VALUE
        }

        for(idx in 1..coins.size-1) {
            for(curAmount in 1..amount) {
	            // curAmount가 현재 코인 종류보다 값이 크면
                if (curAmount >= coins[idx]) {
                    var count = 1
                    var minCoinCount = memo[idx-1][curAmount]
                    // 현재 코인 종류를 1~N개 까지 썼을 떄 해당 curAmount를 만들 수 있는 가장 작은 코인 개수를 구한다.
                    while(curAmount >= coins[idx]*count) {
                        minCoinCount = Math.min(minCoinCount, memo[idx-1][curAmount-(coins[idx]*count)]+count)
                        count++
                    }
                    memo[idx][curAmount] = minCoinCount
                } else {
                    memo[idx][curAmount] = memo[idx-1][curAmount]
                }
            }
        }

		// 마지막 코인 종류의 amount에서 MAX_VALUE가 나왔다는 뜻은 모든 코인을 어떻게 조합하더라도 해당 합계를 만들 수 없음을 뜻한다.
        return if (memo[coins.size-1][amount] == MAX_VALUE) -1 else memo[coins.size-1][amount]
    }
}

3-2. 최적화

3-1의 구현에서 최적화 시킬 수 있는 부분은 아무래도 이중 for문 안에 while문 까지 들어간 곳이 아닐까 싶었다. 조금 더 생각해보니 외부 for문을 코인 종류로 만들었고 내부 for문을 curAmount로 만들었기 때문에 내부 for문이 작동할 때에는 같은 코인 종류를 가지게되고 curAmount는 1씩 증가하기 때문에 이전 curAmount의 값을 가지고 while문을 대체할 수 있게 된다.
그리고 더 나아가서 내부 for문을 도는 동안 한 코인 종류에 대한 합계 결과를 모두 반환하기 때문에 배열을 2D가 아닌 1D만 사용해도 충분할 것 같다는 판단이 들었다.
이 생각을 바탕으로 구현한 결과 159ms에 90.77%로 향상됨을 확인했다.

class Solution {
    var MAX_VALUE = Integer.MAX_VALUE

    fun coinChange(coins: IntArray, amount: Int): Int {
        MAX_VALUE = amount+10 

        return bottomUp2(coins, amount)   
    }

    fun bottomUp2(coins: IntArray, amount: Int): Int {
        val memo = IntArray(amount+1){MAX_VALUE}

        memo[0] = 0

        for(idx in 0..coins.size-1) {
            for(curAmount in 1..amount) {
                if (curAmount >= coins[idx]) {
                    memo[curAmount] = Math.min(memo[curAmount], memo[curAmount-coins[idx]]+1)
                }
            }
        }

        return if (memo[amount] == MAX_VALUE) -1 else memo[amount]
    }
}

4. 복잡도

(3-2. 기준)

시간 복잡도: O(coinsSize*amount)
공간 복잡도: amount